package com.squirrel.michale;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/24 6:57 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0623 {

    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode treeNode = new TreeNode(val);
            treeNode.left = root;
            return treeNode;
        }
        HashMap<TreeNode, Integer> levelMap = new HashMap<>();
        levelMap.put(root, 1);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);
            if (curNodeLevel < depth-1) {
                if (cur.left != null) {
                    levelMap.put(cur.left, curNodeLevel + 1);
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    levelMap.put(cur.right, curNodeLevel + 1);
                    queue.add(cur.right);
                }
            } else if (curNodeLevel == depth - 1) {
                if (cur.left != null) {
                    TreeNode add = new TreeNode(val);
                    add.left = cur.left;
                    cur.left = add;
                }else{
                    TreeNode add = new TreeNode(val);
                    cur.left = add;
                }
                if (cur.right != null) {
                    TreeNode add = new TreeNode(val);
                    add.right = cur.right;
                    cur.right = add;
                }else{
                    TreeNode add = new TreeNode(val);
                    cur.right = add;
                }
            }
        }
        return root;
    }


    public static void main(String[] args) {
        LeetCode0623 leetCode0623 = new LeetCode0623();
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4, null, null), null), new TreeNode(3, null, null));

        int val = 5;
        int depth = 4;
        leetCode0623.addOneRow(root, val, depth);
    }
}
